package tp78.graph.lastVersion;

import java.util.Deque;
import java.util.LinkedList;

public class DiGraph<V, E extends ArcGraph> extends GraphAdjList<V, E> {

	public int inDegree(V v) {
		int count = 0;
		Node node = nodes.get(v);
		for (Node n : getNodes()) { // Recorremos lista de nodos
			if (!n.equals(node)) {
				for (Arc adj : n.adj)
					// Recorremos lista de adyacencia
					if (adj.neighbor.equals(node))
						count++;
			}
		}
		return count;
	}
	
	public int outDegree(V v) {
		Node node = nodes.get(v);
		if (node != null) {
			return node.adj.size();
		}
		return 0;
	}

	/*public String toGraphViz(){
		String aux="";
		
		for(Node n:nodeList){
			for(Arc e:n.adj){
				if(!e.neighbor.visited){
					
				}
			}
			
			
		}
		
	}*/
	
	public boolean containsCicles(){
		for(Node n:nodeList){
			clearMarks();
			if(cicleFindingBFS(n)){
				return true;
			}			
		}
		return false;		
	}

	private boolean cicleFindingBFS(Node n) {
		Deque<Node> q=new LinkedList<Node>();
		Node current=n;
		q.offer(current);
		
		while(!q.isEmpty()){
			current=q.poll();
			if(!current.visited){
				current.visited=true;
			}else{
				return true;
			}
			
			for(Arc e:n.adj){
				if(!e.neighbor.visited){
					e.neighbor.visited=true;
					q.offer(e.neighbor);
				}
			}
			
		}
		return false;
	}
	
	public boolean stronglyConnected(){
		for(Node n:nodeList){
			clearMarks();
			if(BFSCount(n)!=nodes.size()){
				return false;
			}
		}
		return true;
	}
	
	public int BFSCount(Node start){
		Node current;
		Deque<Node> q=new LinkedList<Node>();
		q.offer(start);
		int count=0;
		
		while(!q.isEmpty()){
			current=q.poll();
			if(!current.visited){
				current.visited=true;
				count++;
			}
			
			for(Arc e:current.adj){
				if(!e.neighbor.visited){
					q.offer(e.neighbor);
					count++;
				}
			}
		}
		return count;
	}

	

}
